package common.heap;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 215. 数组中的第K个最大元素
 */
public class _215_FindKthLargest {

    /**
     * 快速排序解法
     */

    public int findKthLargest(int[] nums, int k) {
        return doFindKthLargest(nums, 0, nums.length - 1, k - 1);
    }

    private int doFindKthLargest(int[] nums, int l, int r, int k) {
        if (r == l) {
            return nums[l];
        }
        int target = nums[l];
        int left = l + 1;
        int right = r;
        while (left < right) {
            while (nums[right] <= target && left < right) {
                right--;
            }
            while (nums[left] > target && left < right) {
                left++;
            }
            if (left < right) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
            }
        }
        int temp = nums[l];
        nums[l] = nums[left];
        nums[left] = temp;
        if (right <= k) {
            return doFindKthLargest(nums, right, r, k);
        } else {
            return doFindKthLargest(nums, l, left - 1, k);
        }
    }

    public int findKthLargest2(int[] nums, int k) {
        buildHeap(nums);
        int length = nums.length;
        int heapSize = length;
        for (int i = length - 1; i > length - k; --i) {
            swap(nums, 0, i);
            maxHeap(nums, 0, --heapSize);
        }
        return nums[0];
    }

    private void buildHeap(int[] nums) {
        int length = nums.length;
        for (int i = length / 2; i >= 0; i--) {
            maxHeap(nums, i, length);
        }
    }

    private void maxHeap(int[] nums, int i, int heapSize) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int target = i;
        if (left < heapSize && nums[target] < nums[left]) {
            target = left;
        }
        if (right < heapSize && nums[target] < nums[right]) {
            target = right;
        }
        if (target != i) {
            swap(nums, target, i);
            maxHeap(nums, target, heapSize);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    List<List<String>> result = new ArrayList<>();
    boolean[][] dig = null;


    public List<List<String>> partition(String s) {
        buildDig(s);
        trace(s, new LinkedList<>(), 0, dig);
        return result;
    }

    private void trace(String s, LinkedList<String> traceList, int start, boolean[][] dig) {
        if (start >= s.length()) {
            result.add(new ArrayList<>(traceList));
            return;
        }
        for (int i = start; i < s.length(); i++) {
            if (dig[start][i]) {
                traceList.add(s.substring(start, i + 1));
                trace(s, traceList, i + 1, dig);
                traceList.removeLast();
            }
        }
    }

    private void buildDig(String s) {
        if (s == null || s.length() == 0) {
            return;
        }
        dig = new boolean[s.length()][s.length()];
        for (int i = s.length() - 1; i >= 0; i--) {
            for (int j = i; j < s.length(); j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (j - i <= 1) {
                        dig[i][j] = true;
                    } else {
                        dig[i][j] = dig[i + 1][j - 1];
                    }
                } else {
                    dig[i][j] = false;
                }
            }
        }
    }
}
